package Test.offer;

/**
 * @ClassName P53
 * @Description
 * @Company inspur
 * @Author Kevin
 * @Date 2020/8/2 16:49
 * @Version 1.0
 */
public class P53 {
    public int findOccurTimes(int[] arr, int k) {
        if (arr == null || arr.length <= 0) {
            return 0;
        }
        int startId = findStartIdx(arr, k, 0, arr.length-1);
        int endId = findEndIdx(arr, k, 0, arr.length-1);

        return endId - startId + 1;
    }

    private int findEndIdx(int[] arr, int k, int start, int end) {
        int mid;
        while (start <= end) {
            mid = start + ((end - start)>>1);
            if (arr[mid] > k) {
                end = mid - 1;
            } else if (arr[mid] < k) {
                start = mid + 1;
            } else {
                if (mid == end || arr[mid+1] != arr[mid]) return mid;
                else end = mid -1;
            }
        }
        return -1;
    }

    private int findStartIdx(int[] arr, int k, int start, int end) {
        int mid;
        while (start <= end) {
            mid = start + ((end - start)>>1);
            if (arr[mid] > k) {
                end = mid - 1;
            } else if (arr[mid] < k) {
                start = mid + 1;
            } else {
                if (mid == 0 || arr[mid-1] != arr[mid]) return mid;
                else start = mid+1;
            }
        }
        return -1;
    }
}
